Andrey Andreyevich Vlasov sinh ngày 14/9/1901 tại làng Lomakino tỉnh Nhizegorod trong một gia đình nông dân nghèo đông con. Andrey là con trai út trong số các anh em trai (gia đình có 13 người con). Ông bố mong muốn các con mình được học hành tử tế, nhưng do gia đình quá nghèo nên không thể thực hiện được mong ước ấy. Người anh cả của Andrey là Ivan đã bỏ học đi làm và nuôi Andrey ăn học.

Andrey được đào tạo để trở thành cha cố - sau khi tốt nghiệp trường dòng, ông vào học tại Chủng viện Nhizegorod. Ngay từ nhỏ cậu bé Andrey đã thể hiện mình có một trí thông minh sắc sảo và khả năng nhanh chóng hòa nhập với thế giới xung quanh. Nhưng khi hiểu rằng, chính quyền Xô Viết mới thành lập sẽ không thương xót gì các cha cố, Andrey bỏ ngay chủng viện và đến học tại trường nông nghiệp để trở thành kỹ sư canh nông.

Năm 1919, Vlasov được gọi nhập ngũ (Hồng quân Liên Xô). Chàng trai sáng dạ Andrey đã học qua chùng viện được cử đi học khóa đào tạo chỉ huy 4 tháng và sau khi tốt nghiệp được phân về đơn vị. Viên trung đội trưởng trẻ này đã chiến đấu dũng cảm trong giai đoạn kết thúc nội chiến và tiếp tục thăng tiến trên con đường binh nghiệp sau nội chiến kết thúc.